/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/reverse-pairs
   @Language: C++
   @Datetime: 19-04-02 10:32
   */

class Solution {
public:
	/**
	 * @param A: an array
	 * @return: total of reverse pairs
	 */
	long long reversePairs(vector<int> &A) {
		// write your code here
		vector<int> B;
		long long res=0;
		for(int i=A.size(); i--;){
			auto pos=lower_bound(B.begin(),B.end(),A[i]);
			res+=pos-B.begin();
			B.insert(pos,A[i]);
		}
		return res;
	}
};
